/**
 * @ClassName chapter1.KP4_selectsort
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/10/7 14:24
 */

import java.util.Arrays;

/**
 * 查询相应区间的数组元素之和
 */
public class KP6_querysum {

    // ==================================================================================
    // ===============                    方法一                           ===============
    // ==================================================================================

    /**
     * 生成所有区间求和的二维表格
     *
     * @return
     */
    public static int[][] createTable(int[] array) {
        int length = array.length;
        int[][] table = new int[length][length];
        for (int i = 0; i < length; i++) {
            table[i][i] = array[i];
            for (int j = i + 1; j < length; j++) {
                table[i][j] = table[i][j - 1] + array[j];
            }
        }
        return table;
    }

    /**
     * 查询数组区间
     *
     * @param array
     */
    public static int queryArraySum(int[] array, int row, int col) {
        int[][] table = createTable(array);
        return table[row - 1][col - 1];
    }

    public static void printArray(int[][] array) {
        for (int[] row : array) {
            for (int col : row) {
                if (col != 0) {
                    System.out.printf("%-4d", col);
                } else {
                    System.out.printf("%-4s", "");
                }
            }
            System.out.println();
        }
    }

    public static void main1(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        printArray(createTable(array));
        System.out.println(queryArraySum(array, 3, 7));
    }

    // ==================================================================================
    // ===============                    方法二                           ===============
    // ==================================================================================


    /**
     * 生成0~i区间原数组元素求和的新数组
     * @return
     */
    public static int[] createArray(int[] array) {
        int length = array.length;
        int[] newArray = new int[length];
        newArray[0] = array[0];
        for (int i = 1; i < length; i++) {
            newArray[i] = newArray[i - 1] + array[i];
        }
        return newArray;
    }

    public static int queryArraySum2(int[] array, int L, int R) {
        int[] newArray = createArray(array);
        //return L == 0 ? newArray[R] : newArray[R] -newArray[L-1];
        return L == 1 ? newArray[R-1] : newArray[R-1] -newArray[L-2];
    }


    // ==================================================================================
    // ===============                    方法三                           ===============
    // ==================================================================================

    public static int queryArraySum3(int[] array, int L, int R) {
       int sum = 0;
       for (int i = L-1; i < R; i++) {
           sum += array[i];
       }
       return sum;
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(Arrays.toString(createArray(array)));
        System.out.println(queryArraySum2(array,3,7));
        System.out.println(queryArraySum3(array,3,7));
    }

}
